The present invention relates to the field of automatic synthesis of complex structures; more particularly, the present invention relates to the automatic synthesis of the topology and parameter values for controllers and control systems.
Controllers (control systems) are ubiquitous in industry. A purpose of a controller is to solicit an actual response of a system that is to be controlled (conventionally called the plant) to match a desired response (called the reference signal or command signal).
There are many different measures of merit that are commonly used for controllers. For example, it is common to want to minimize the time required to bring about the desired response of the plant. For example, the occupant of a chilly room may set a thermostat to request that the room temperature be raised to 70 degrees. The reference signal is 70 degrees. The controller causes fuel to flow into the furnace so as to cause the furnace to heat the room to 70 degrees. As the temperature of the room is rising, the controller may measure the difference between the reference signal (the desired temperature) and the room""s actual temperature (the plant response). The measure of merit for this controller may be based on the amount of time it takes to warm the room to the desired temperature.
The measure of merit for a controller typically involves several different (and usually conflicting) considerations. For example, in addition to wanting to minimize the time required to bring about the desired change in the plant, it is also common to simultaneously want to avoid significantly overshooting the desired values for the plant response. For example, although the occupant wants the temperature to reach 70 degrees quickly, he doesn""t want to accomplish this goal by first raising the temperature to 110 degrees (overshooting the reference signal) and then letting the room cool to the desired 70 degrees. In fact, it would be ideal if the temperature quickly rose to 70 degrees without any overshoot above 70 degrees.
The cost of energy is often a major additional competing consideration in measuring the merit of a controller. Different strategies for causing a plant to reach a desired state generally have a different cost in terms of the cost of energy. Thus, the measure of merit for a controller may consist of a specified mixture reflecting the time required to bring about the desired change in the plant, the energy required to effect the change, and the avoidance of overshoot.
In addition to the above considerations, it is common to place certain practical limits on the value of the control variable(s) so that the plant is not presented with extreme values for the control variable(s). For example, a limiter would prevent a control variable from heating the room to 110 degrees. Similarly, it is common to place certain practical limits on the plant""s internal state variables so that they do not exceed certain prespecified limits.
Furthermore, since all real world plants and controllers are imperfect devices, it is also desirable that a controller operate robustly in the face of perturbations or disturbances in the actual behavior of the plant or controller. It is also desirable to suppress and ignore high frequency noise in the reference signal, the control variable, and the actual plant response.
Real-world controllers must consider the fact that the actual value of a control variable must be finite (e.g., cannot be an impulse of infinite amplitude) and that real-world plants do not respond instantaneously.
Many, if not most, real-world controllers are operated manually. However, the focus here is on automatic controllersxe2x80x94that is, controllers that automatically process reference signal(s) and plant output(s) (and possibly other inputs) in order to create the control signals.
The underlying principles of controllers are broadly the same whether the system is mechanical, electrical, thermodynamic, hydraulic, biological, economic, etc. and whether the variable of interest is temperature, velocity, voltage, water pressure, interest rates, heart rate, humidity, etc. Moreover, many controllers incorporate elements from several different engineering domains. For example, the variable of interest for a home heating system is temperature, the setting of the thermostat and the room""s current temperature are usually converted into an electrical signal, these electrical signals are usually processed by an electrical controller (analog or digital), the control mechanism is usually a mechanical valve that permits oil to flow into the furnace, while the furnace is a thermodynamic system.
In spite of the multidisciplinary aspects of control engineering, there are several reasons why it is often convenient to discuss controllers in purely electrical terms. First, many real-world sensors, reference signals, control variables, and controllers are, in fact, electrical. Second, regardless of whether the controller or plant is actually electrical, control engineers often use electrical terminology as a common language for modeling plants and controllers. Third, it is possible to use electrical simulators, such as the SPICE simulator (described in SPICE 3 Version 3F5 User""s Manual by Thomas Quarles, A. R. Newton, D. O. Pederson, and A. Sangiovanni-Vincentelli, Department of Electrical Engineering and Computer Science, University of California, Berkeley, Calif.: 1994) for solving control problems. Electrical simulators are useful because the systems of simultaneous integro-differential equations used in electrical engineering also apply to many aspects of control engineering.
Design is a major activity of practicing engineers. Engineers are often called upon to design controllers that satisfy certain prespecified high-level design goals. The creation of a design for a complex structure, such as a controller, typically involves intricate tradeoffs between competing considerations. Design is ordinarily thought to require human intelligence.
Controllers can be composed of a variety of types of one or more signal processing blocks that process signals in the time-domain, including, for example, but not limited to, gain, lead, lag, integrator, differentiator, adder, inverter, subtractor, and multiplier. Each of these processing blocks has one or more inputs and a single output. The input to a controller typically consists of the reference signal(s) and the plant response(s) or, sometimes, just the difference (error) between each reference signal and the corresponding plant response. The output of a controller consists of control variable(s) that are passed to the plant.
One or more parameter values are required to completely specify many of the signal processing blocks used in controllers. For example, the complete specification of a gain block requires specification of its amplification factor (e.g., 100-to-1 or 40 decibel amplification). The specification of these parameter values (which are typically numerical values) is sometimes called the xe2x80x9csizing.xe2x80x9d
The individual signal processing blocks of a controller are coupled to one another in a particular topological arrangement. The topology of a controller entails the specification of the total number of processing blocks to be employed in the controller, the type of each block (e.g., gain, lead, lag, integrator, differentiator, adder, inverter, subtractor, and multiplier), and the connections between the input point(s) and the output point of each block in the controller.
The design (e.g., synthesis) of a controller requires specification of both the topology and parameter values (sizing) such that the controller satisfies certain user specified high-level design requirements.
Controllers may be designed using purely analytical methods. Search techniques offer a potential way to discover a satisfactory solution to a problem when no analytical method is available.
There are many techniques for searching a space of candidate designs for an optimal or near-optimal controller (e.g., point in the search space), including, but not limited to, hill climbing, simulated annealing, and genetic programming.
A search through any search space is an iterative process that involves starting with one or more entities (points) from the search space, ascertaining the merit of the entity for solving the problem at hand, creating a new candidate entity by modifying existing entity(ies), ascertaining the merit of the new candidate entity, and using the merit measure to select among entities. The measure or merit is typically called the xe2x80x9cfitness measurexe2x80x9d when referring to genetic programming, the xe2x80x9cenergy levelxe2x80x9d when referring to simulated annealing, and the xe2x80x9cobjective functionxe2x80x9d measure when referring to hill climbing. Some of the other additional terms that are commonly used for merit include payoff, score, and profit. The term xe2x80x9cfitnessxe2x80x9d will be used herein to refer to the conception of xe2x80x9cmerit.xe2x80x9d The individual steps of the iterative search process are typically called xe2x80x9cgenerationsxe2x80x9d when referring to genetic programming, xe2x80x9ctime-stepsxe2x80x9d or xe2x80x9ccyclesxe2x80x9d when referring to simulated annealing, and xe2x80x9cstepsxe2x80x9d when referring to hill climbing.
Search techniques do not find solutions by analysis and proof. Instead, they search a space for a solution. Consequently, search techniques typically require large amounts of computation. As S. P. Boyd and C. H. Barratt stated in Linear Controller Design: Limits of Performance (Prentice Hall, Englewood Cliffs, N.J.:1991, page 11) in discussing the xe2x80x9cchallenges for controller design,xe2x80x9d
The challenge for controller design is to productively use the enormous computing power available. Many current methods of computer-aided controller design simply automate procedures developed in the 1930""s through the 1950""s, for example, plotting root loci or Bode plots. Even the xe2x80x98modernxe2x80x99 state-space and frequency-domain methods (which require the solution of algebraic Riccati equations) greatly underutilize available computing power.
Search by Use of Hill Climbing
Simple hill climbing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. The new candidate entity is created by a problem-specific modification operation (often a probabilistic operation) that modifies the current entity (point) in the search space in order to obtain a new (usually nearby) candidate entity in the search space. In hill climbing, a new candidate point with a better fitness than the preexisting point is unconditionally selected. Hill climbing is a point-to-point search technique in the sense that the search proceeds from a single point in the search space of the problem to another single point.
Conducting a search using hill climbing through a space of entities in a nontrivial problem very often results in the search becoming trapped at a local optimum point rather than finding the global optimum point of the search space. In hill climbing (and all other search techniques), it may be necessary to make multiple runs (assuming that the problem-specific modification operation is probabilistic so that different runs can potentially produce different outcomes).
Search by Use of Simulated Annealing
Simulated annealing (Optimization by simulated annealing, by S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, in Science 220, 1983, pages 671-68) resembles hill climbing in that it is a point-to-point search technique. Like hill climbing, simulated annealing employs a problem-specific probabilistic modification operation (typically termed a xe2x80x9cmutationxe2x80x9d when referring to simulated annealing) for modifying the current entity (point) in the search space in order to obtain a new candidate entity. At each step of the search, the current point in the search space is modified using the modification operator and the new point""s fitness is ascertained.
Specifically, simulated annealing involves starting with a single initial entity (point) in the search space, ascertaining the fitness of the entity, creating a new candidate entity, ascertaining the fitness of the new candidate entity, and using the fitness measure to select between the preexisting entity and the new candidate entity. Simulated annealing always selects the new candidate entity if it is better than the preexisting entity. That is, it operates in the same way as hill climbing in such cases.
However, simulated annealing differs from hill climbing in the way it handles the case when the new candidate entity is worse than the preexisting entity. In this case, the Metropolis algorithm and the Boltzmann equation are applied to determine whether to accept a non-improving new candidate entity. A run of simulated annealing is governed by an annealing schedule in which a temperature T changes as the run proceeds (typically in an exponentially monotonically decreasing way). The effect of the Metropolis algorithm and the Boltzmann equation are that the probability of acceptance of a non-improving modification is greater if the fitness difference is small or if the temperature T is high. Thus, fairly large non-improving modifications are likely to be accepted early in the run (when the temperature is high). That is, simulated annealing resembles blind random search in early stages of the run. However, later in the run (when the system has cooled), only small non-improving modifications are likely to be accepted. That is, simulated annealing resembles hill climbing in later stages of the run. If a modification is not accepted at any step of the run of simulated annealing, the probabilistic modification operator is re-invoked to produce another new point.
Search by Use of Genetic Programming
xe2x80x9cGenetic programmingxe2x80x9d (also referred to as the xe2x80x9cnon-linear genetic algorithmxe2x80x9d or the xe2x80x9chierarchical genetic algorithmxe2x80x9d in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection, by John R. Koza, Cambridge, Mass.: The MIT Press, 1992; the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs, by John R. Koza, Cambridge, Mass.: The MIT Press, 1994; Genetic Programming III: Darwinian Invention and Problem Solving by John R. Koza, Forrest H Bennett III, David Andre, and Martin A. Keane, San Francisco, Calif.; Morgan Kaufmann Publishers, 1999; and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, 5,343,554, 5,742,738, and 5,867,397.
Genetic programming is referred to as xe2x80x9cnon-linearxe2x80x9d or xe2x80x9chierarchicalxe2x80x9d because the original genetic algorithm described by John H. Holland in Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, Ann Arbor, Mich.: University of Michigan Press, Second edition, Cambridge, Mass.: The MIT Press, 1975, operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes.
Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming may start with a xe2x80x9cprimordial oozexe2x80x9d of randomly generated programs composed of the available programmatic ingredients. It then applies the principles of animal husbandry to breed a new (and often improved) population of programs. Genetic programming may perform the breeding in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of learning associated with Holland""s genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs by John R. Koza, Cambridge, Mass.: The MIT Press, 1994, genetic programming can evolve multi-part programs having a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs). See U.S. Pat. No. 5,343,554, entitled xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functionsxe2x80x9d, issued Aug. 30, 1994, by Koza, John R., and Rice, James P.
The architecture of a multi-part program may consist of a result-producing branch and automatically defined function(s) and involves:
(1) the total number of automatically defined functions,
(2) the number of arguments (if any) possessed by each automatically defined function, and
(3) if there is more than one automatically defined function in a program, the nature of the hierarchical references (including recursive references), if any, allowed among the automatically defined functions.
There are a variety of ways of determining the architecture for a computer program that is to be evolved using genetic programming, such as
(1) the human user may pre-specify the architecture of the overall program as part of his or her preparatory steps prior to launching the run; and
(2) architecture-altering operations may be used during the run to automatically create the architecture of the program during the run.
Architecture-altering operations, such as described in Genetic Programming III: Darwinian Invention and Problem Solving (1999), enable genetic programming to automatically determine the number of subroutines, the number of arguments that each possesses, and the nature of the hierarchical references, if any, among such automatically defined functions. See U.S. Pat. No. 5,742,738, entitled xe2x80x9cSimultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,xe2x80x9d issued Apr. 21, 1998, by Koza, John R., Andre, David, and Tackett, Walter Alden. Certain additional architecture-altering operations also enable genetic programming to automatically determine whether and how to use internal memory, iterations, and recursion in evolved programs. See Genetic Programming III: Darwinian Invention and Problem Solving by John R. Koza, Forrest H Bennett III, David Andre, and Martin A. Keane, San Francisco, Calif.; Morgan Kaufmann Publishers, 1999.
Genetic programming has been successfully used to solve many difficult problems involving the search of complex spaces. For example, genetic programming has been used for automatically creating the topology and sizing for an analog electrical circuit from a high-level statement of the circuit""s desired behavior. See U.S. Pat. No. 5,867,397, entitled xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures Using Genetic Programming,xe2x80x9d issued Feb. 2, 1999.
Genetic programming may breed computer programs to solve problems by executing the following steps:
(1) Generate an initial population of random compositions (i.e., programs) of the functions and terminals of the problem.
(2) Iteratively perform the following substeps (referred to herein as a generation) on the population until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of programs by applying the following operations. The operations are applied to program(s) selected from the population with a probability based on fitness (with reselection allowed).
(i) Reproduction: Copy the selected program to the new population.
(ii) Crossover: Create a new offspring program for the new population by recombining randomly chosen parts of two selected programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of the selected program.
(iv) Architecture-altering operations: Select an architecture-altering operation from the available repertoire of such operations and create one new offspring program for the new population by applying the selected architecture-altering operation to the selected program.
(3) Designate the individual program that is identified by result designation (e.g., the best-so-far individual) as the result of the run of genetic programming. This result may be a solution (or an approximate solution) to the problem.
Genetic programming conducts a search for a solution, or approximate solution, to a problem.
Simulated annealing is similar to genetic programming in that it sometimes accepts a newly created point that is known to be inferior in the hope that it will lead to better points. That is, neither simulated annealing nor genetic programming is a purely greedy search algorithm. Simulated annealing differs from genetic programming in that simulated annealing unconditionally accepts an improving modification while genetic programming does not always do this. Simulated annealing and hill climbing differ from searches conducted by the genetic programming in that simulated annealing and hill climbing are point-to-point search techniques. That is, only one entity (point) is retained at each generation of the search in simulated annealing or hill climbing. There is no population of entities in simulated annealing or hill climbing (as there is in genetic programming). Because there is no population in simulated annealing or hill climbing, there is no analog to the crossover operation of genetic programming (where two parents mate, or recombine, to produce offspring).
Genetic programming is preferable to hill climbing because hill climbing operates on only a single entity (point) in the search space of the problem and because hill climbing greedily unconditionally selects a better point in preference to a worse point. Because of this, hill climbing tends to become trapped on local optimum points that are not global optimum points. Simulated annealing also operates on a single entity (point) in the search space of the problem; however, simulated annealing is preferable to hill climbing because it typically uses the Metropolis algorithm and the Boltzmann equation to avoid becoming entrapped on locally optimum points.
Genetic programming is preferable to simulated annealing (which resembles a genetic algorithm operating on a population of size 1) because the existence of a population greater than one permits crossover (recombination) to occur between two (or more) parents, each chosen probabilistically based on their fitness. Experience indicates that the recombination of parts of already fit parents often yields superior offspring in a far more rapid way than that provided by search techniques that lack recombination.
There has been extensive previous work on the problem of automating various aspects of the design of controllers using non-analytic search techniques such as simulated annealing, artificial intelligence, genetic algorithms, and fuzzy logic. Many of the preexisting techniques address only the aspect of automatically determining the parameter values (sizing) of the processing blocks of the controller. Many of these techniques require the user to supply a reasonably good working controller as a starting point. Many of the techniques require repeated interactive intervention by the human user during the design process. Generally, the decisions that are automated are only a small subset of the decisions that must be made in solving a non-trivial problem.
Genetic programming has been previously applied to certain simple control problems, including discrete-time problems where the evolved program receives the system""s current state as input, performs an arithmetic or conditional calculation on the inputs, and computes a value for a control variable. These techniques have been applied to problems of cart centering, broom balancing, backing a tractor-trailer truck to a loading dock, controlling the food foraging strategy of a lizard, and navigating a robot with a nonzero turning radius to a destination point (called the xe2x80x9cfly toxe2x80x9d problem when applied to aircraft). See Koza, John R and Keane, Martin A., Cart centering and broom balancing by genetically breeding populations of control strategy programs. In Proceedings of International Joint Conference on Neural Networks. Washington, Jan. 15-19, 1990. Hillsdale, N.J.: Lawrence Erlbaum. Volume I; Koza, John R and Keane, Martin A., Genetic breeding of non-linear control strategies for broom balancing. In Proceedings of the Ninth International Conference on Analysis and Optimization of Systems. Antibes, France, June, 1990. Berlin: Springer-Verlag; and Koza, John R., Forrest H Bennett, III, David Andre, and Martin Keane, Genetic Programming III: Darwinian Invention and Problem Solving, San Francisco, Calif.: Morgan Kaufman, 1999. In addition, genetic programming has been previously used to evolve an analog electrical circuit for a discrete-time robotic controller (Koza, John R., Forrest H Bennett, III, David Andre, and Martin Keane, Genetic Programming III: Darwinian Invention and Problem Solving, San Francisco, Calif.: Morgan Kaufman, 1999).
U.S. Patents
U.S. Pat. No. 4,697,242, xe2x80x9cAdaptive Computing System Capable of Learning and Discoveryxe2x80x9d, issued Sep. 29, 1987, Holland et al.
U.S. Pat. No. 4,881,178, xe2x80x9cMethod of Controlling a Classifier System,xe2x80x9d issued Nov. 14, 1989, Holland et al.
U.S. Pat. No. 4,935,877, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems,xe2x80x9d issued Jun. 19, 1990, Koza.
U.S. Pat. No. 5,136,686, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions,xe2x80x9d issued Aug. 4, 1992, Koza.
U.S. Pat. No. 5,148,513, xe2x80x9cA Non-Linear Genetic Process for Use with Plural Co-Evolving Populations,xe2x80x9d issued Sep. 15, 1992, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,343,554, xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions,xe2x80x9d issued Aug. 30, 1994, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,742,738, xe2x80x9cSimultaneous Evolution of the Architecture of a Multi-part Program to Solve a Problem Using Architecture Altering Operations,xe2x80x9d issued Apr. 21, 1998, Koza, John R., Andre, David, and Tackett, Walter Alden.
U.S. Pat. No. 5,867,397, xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures Using Genetic Programmingxe2x80x9d, issued Feb. 2, 1999, Koza, John R., Bennett III, Forrest H, and Andre, David.
Anderson, Bjorn, Svensson, Per, Nordin, Peter, and Nordahl, Mats. 1999. Reactive and memory-based genetic programming for robot control. In Poli, Riccardo, Nordon, Peter, Langdon, William B., and Fogarty, Terence C. 1999. Genetic Programming: Second European Workshop. EuroGP""99. Proceedings. Lecture Notes in Computer Science. Volume 1598. Berlin, Germany: Springer-Verlag. Pages 161-172.
Angeline, Peter J. 1997. An alternative to indexed memory for evolving programs with explicit state representations. In Koza, John R., Deb, Kalyanmoy, Dorigo, Marco, Fogel, David B., Garzon, Max, Iba, Hitoshi, and Riolo, Rick L. (editors). Genetic Programming 1997: Proceedings of the Second Annual Conference, Jul. 13-16, 1997, Stanford University. San Francisco, Calif.: Morgan Kaufmann. Pages 423-430.
Angeline, Peter J. 1998a. Multiple interacting programs: A representation for evolving complex behaviors. Cybernetics and Systems. 29(8) 779-806.
Angeline, Peter J. 1998b. Evolving predictors for chaotic time series. In Rogers, S., Fogel, D., Bezdek, J., and Bosacchi, B. (editors). Proceedings of SPIE (Volume 3390): Application and Science of Computational Intelligence, Bellingham, Wash.: SPIExe2x80x94The International Society for Optical Engineering. Pages 170-180.
Angeline, Peter J. and Fogel, David B. 1997. An evolutionary program for the identification of dynamical systems. In Rogers, S. (editor). Proceedings of SPIE (Volume 3077): Application and Science of Artificial Neural Networks III. Bellingham, Wash.: SPIExe2x80x94The International Society for Optical Engineering. Pages 409-417.
Astrom, Karl J. and Hagglund, Tore. 1995. PID Controllers: Theory, Design, and Tuning. Second Edition. Research Triangle Park, N.C.: Instrument Society of America.
Banzhaf, Wolfgang, Nordin, Peter, Keller, Robert E., and Francone, Frank D. 1998. Genetic Programmingxe2x80x94An Introduction. San Francisco, Calif.: Morgan Kaufmann and Heidelberg: dpunkt.
Banzhaf, Wolfgang, Nordin, Peter, Keller, and Olmer, Markus. 1997. Generating adaptive behavior for a real robot using function regression with genetic programming. In Koza, John R., Deb, Kalyanmoy, Dorigo, Marco, Fogel, David B., Garzon, Max, Iba, Hitoshi, and Riolo, Rick L. (editors). Genetic Programming 1997: Proceedings of the Second Annual Conference, Jul. 13-16, 1997, Stanford University. San Francisco, Calif.: Morgan Kaufmann. Pages 3514 43.
Boyd, S. P. and Barratt, C. H. 1991. Linear Controller Design: Limits of Performance. Englewood Cliffs, N.J.: Prentice Hall.
Crawford, L. S., Cheng, V. H. L. and Menon, P. K. 1999. Synthesis of flight vehicle guidance and control laws using genetic search methods. Proceedings of 1999 Conference on Guidance, Navigation, and Control. Reston, Va.: American Institute of Aeronautics and Astronautics. Paper AIAA-99-4153.
Dewell, Larry D. and Menon, P. K. 1999. Low-thrust orbit transfer optimization using genetic search. Proceedings of 1999 Conference on Guidance, Navigation, and Control. Reston, Va.: American Institute of Aeronautics and Astronautics. Paper AIAA-99-4151.
Dorf, Richard C. and Bishop, Robert H. 1998. Modern Control Systems. Eighth edition. Menlo Park, Calif.: Addison-Wesley.
Friedman, George J., 1956. Selective Feedback Computers for Engineering Synthesis and Nervous System Analogy. Master""s thesis. University of California at Los Angeles. In Fogel, David B. 1998. Evolutionary Computation: The Fossil Record (editor). Piscataway, N.J.: IEEE Press. Pages 29-84.
Holland, John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, Mich.: University of Michigan Press. Second edition. Cambridge, Mass.: The MIT Press, 1975.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, pages 671-680.
Koza, John R., and Keane, Martin A. 1990a. Cart centering and broom balancing by genetically breeding populations of control strategy programs. In Proceedings of International Joint Conference on Neural Networks, Washington, Jan. 15-19, 1990. Hillsdale, N.J.: Lawrence Erlbaum. Volume I, Pages 198-201.
Koza, John R., and Keane, Martin A. 1990b. Genetic breeding of non-linear optimal control strategies for broom balancing. In Proceedings of the Ninth International Conference on Analysis and Optimization of Systems. Antibes, France, Jun., 1990. Berlin: Springer-Verlag. Pages 47-56.
Koza, John R., Forrest H Bennett, III, David Andre, and Martin Keane. 1999. Genetic Programming III: Darwinian Invention and Problem Solving, San Francisco, Calif.: Morgan Kaufman, 1999.
Koza, John R., Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Mass.: The MIT Press, 1992.
Koza, John R., Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, Mass.: The MIT Press, 1994.
Man, K. F., Tang, K. S., Kwong, S., and Halang, W. A. 1997. Genetic Algorithms for Control and Signal Processing. London: Springer-Verlag.
Man, K. F., Tang, K. S., Kwong, S., and Halang, W. A. 1999. Genetic Algorithms: Concepts and Designs. London: Springer-Verlag.
Marenbach, Peter, Bettenhausen, Kurt D., and Freyer, Stephan. 1996. Signal path oriented approach for generation of dynamic process models. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors). Genetic Programming 1996: Proceedings of the First Annual Conference, Jul. 28-31, 1996, Stanford University. Cambridge, Mass.: MIT Press. Pages 327-332.
Menon, P. K., Yousefpor, M., Lam, T., and Steinberg, M. L. 1995. Nonlinear flight control system synthesis using genetic programming. Proceedings of 1995 Conference on Guidance, Navigation, and Control. Reston, Va.: American Institute of Aeronautics and Astronautics. Pages 461-470.
Nordin, Peter. 1997. Evolutionary Program Induction of Binary Machine Code and its Application. Munster, Germany: Krehl Verlag.
Ogata, Katsuhiko. 1997. Modern Control Engineering. Third edition. Upper Saddle River, N.J.: Prentice Hall.
Quarles, Thomas, Newton, A. R., Pederson, D. O., and Sangiovanni-Vincentelli, A. 1994. SPICE 3 Version 3F5 User""s Manual. Department of Electrical Engineering and Computer Science, University of California, Berkeley, Calif. March 1994.
Sterling, Thomas L., Salmon, John, and Becker, Donald J., and Savarese, How to Build a Beowulf: A Guide to Implementation and Application of PC Clusters. Cambridge, Mass.: The MIT Press, 1999.
Sweriduk, G. D., Menon, P. K., and Steinberg, M. L. 1998. Robust command augmentation system design using genetic search methods. Proceedings of 1998 Conference on Guidance, Navigation, and Control. Reston, Va.: American Institute of Aeronautics and Astronautics. Pages 286-294.
Sweriduk, G. D., Menon, P. K., and Steinberg, M. L. 1999. Design of a pilot-activated recovery system using genetic search methods. Proceedings of 1998 Conference on Guidance, Navigation, and Control. Reston, Va.: American Institute of Aeronautics and Astronautics.
Teller, Astro. 1998. Algorithm Evolution with Internal Reinforcement for Signal Understanding. PhD Thesis. Computer Science Department. Carnegie Mellon University. Pittsburgh, Pa.
Teller, Astro. 1999. The internal reinforcement of evolving algorithms. In Spector, Lee, Langdon, William B., O""Reilly, Una-May, and Angeline, Peter (editors). 1999. Advances in Genetic Programming 3. Cambridge, Mass.: The MIT Press. Pagesxe2x80x94.
Thompson, Adrian. 1998. Hardware Evolution: Automatic Design of Electronic Circuits in Reconfigurable Hardware by Artificial Evolution. London: Springer-Verlag.
Whigham, Peter A. 1995b. Grammatically-based genetic programming. In Rosca, Justinian (editor). Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications. University of Rochester. National Resource Laboratory for the Study of Brain and Behavior. Technical Report 95-2. Jun. 1995. Pages 33-41.
Whitley, Darrell, Gruau, Frederic, and Preatt, Larry. 1995. Cellular encoding applied to neurocontrol. In Eshelman, Larry J. (editor). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, Calif.: Morgan Kaufmann. Pages 460-467.
A method and apparatus for the automatic creation of the topology and parameter values for controllers. An iterative process may be run to create a design of a structure that satisfies prespecified high-level design goals. In one embodiment, the present invention operates with a system having a population of entities of various sizes and shapes.